home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 October: Mac OS SDK / Dev.CD Oct 96 SDK / Dev.CD Oct 96 SDK2.toast / Development Kits (Disc 2) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc Source Code / Imaging / PolygonClipper / PGEdge.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1996-04-22  |  9.9 KB  |  428 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        PGEdge.cpp
  3.  
  4.     Contains:    Active-edge structure for the clipper.
  5.  
  6.     Owned by:    Jens Alfke (based on algorithm by A. C. Kilgour)
  7.  
  8.     Copyright:    © 1994 - 1995 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     Change History (most recent first):
  11.     
  12.          <6>     8/16/95    NP        1274946: ErrorDef.idl problems. Add include
  13.                                     file.
  14.          <5>     3/20/95    jpa        Another fix to TestPoint, from Chuck
  15.                                     Dumont. [1186959]
  16.          <4>     12/5/94    jpa        Fixed a bug in TestPoint, thanks to Chuck
  17.                                     Dumont. [1203950]
  18.          <3>     9/29/94    RA        1189812: Mods for 68K build.
  19.          <2>     6/17/94    jpa        Include AltPoint and AltPoly.
  20.          <1>     6/15/94    jpa        first checked in
  21.          ---------------------------Moved to ODSOM project.
  22.          <3>     5/27/94    jpa        Fixed a possible bug that I noticed.
  23.          <2>     5/10/94    jpa        Tweaked a comparison to appease #%$*
  24.                                     cfront.
  25.          <1>      5/9/94    jpa        first checked in
  26.          
  27.     Theory of Operation:
  28.         A. C. Kilgour, "Polygon Processing For VLSI Pattern Generation"
  29.         In Rogers & Earnshaw, "Techniques For Computer Graphics"
  30.         Springer-Verlag, 1987
  31.         
  32.         A PGEdgeTable represents the active-edge table as a LinkedList
  33.         of PGEdges. A PGEdge points to its endpoints and to its output
  34.         contour (if any) and has some other flags used during processing.
  35.     
  36.     In Progress:
  37.         
  38. */
  39.  
  40.  
  41. #pragma segment ODPolygonClip
  42.  
  43.  
  44. #ifndef _ALTPOINT_
  45. #include "AltPoint.h"
  46. #endif
  47.  
  48. #ifndef _ALTPOLY_
  49. #include "AltPoly.h"
  50. #endif
  51.  
  52. #ifndef _PGEDGE_
  53. #include "PGEdge.h"
  54. #endif
  55.  
  56. #ifndef _PGPOLY_
  57. #include "PGPoly.h"
  58. #endif
  59.  
  60. #ifndef _LINEOPS_
  61. #include "LineOps.h"
  62. #endif
  63.  
  64. #ifndef _EXCEPT_
  65. #include "Except.h"
  66. #endif
  67.  
  68. #ifndef _ODMATH_
  69. #include "ODMath.h"
  70. #endif
  71.  
  72. #ifndef _ODDEBUG_
  73. #include "ODDebug.h"
  74. #endif
  75.  
  76. #ifndef _UTILERRS_
  77. #include "UtilErrs.h"
  78. #endif
  79.  
  80. #include <string.h>
  81.  
  82.  
  83. //=============================================================================
  84. // PGEdge
  85. //=============================================================================
  86.  
  87.  
  88. PGEdge::PGEdge( const PGVertex *tail, const PGVertex *head )
  89.     :fWrapNo(0),
  90.      fLowEvent(kODFalse),
  91.      fMatched(kODFalse),
  92.      fLeftBundle(kODFalse),
  93.      fRightBundle(kODFalse),
  94.      fSense(Compare(head,tail)),    // Edge goes from tail to head!
  95.      fOtherSide(kODNULL),
  96.      fOutput(kODNULL)
  97. {
  98.     if( fSense == kPositive ) {
  99.         fHighVert = tail;
  100.         fLowVert = head;
  101.     } else {
  102.         fHighVert = head;
  103.         fLowVert = tail;
  104.     }
  105.     fDelta =  fLowVert->AsPoint();
  106.     fDelta-= fHighVert->AsPoint();        // fDelta.y >= 0!
  107. }
  108.  
  109.  
  110. PGEdge*
  111. PGEdge::ReplaceWithCopy( )
  112. {
  113.     // When an edge that continues below an event is moved to the lower edge list,
  114.     // a copy is left above for matching. The copy has to inherit most of the edge's
  115.     // characteristics, like its list membership and its output contour.
  116.     
  117.     PGEdge *copy = new PGEdge(*this);
  118.     
  119.     this->GetPrevious()->SetNext(copy);
  120.     this->GetNext()->SetPrevious(copy);
  121.     
  122.     this->SetPrevious(kODNULL);
  123.     this->SetNext(kODNULL);
  124.     
  125.     if( fOutput ) {
  126.         fOutput = kODNULL;
  127.         fOtherSide->fOtherSide = copy;
  128.         fOtherSide = kODNULL;
  129.     }
  130.     
  131.     return copy;
  132. }
  133.  
  134.  
  135. PGSide
  136. PGEdge::TestPoint( const ODPoint &pt )
  137. {
  138.     // Since we have to multiply two Fracts, we use the Mac Toolbox's
  139.     // LongMul routine, which multiplies two 32-bit values producing a
  140.     // 64-bit result. Since Fixeds are just scaled longs, we can use this
  141.     // since all we are doing is comparing the results.
  142.     
  143.     // Our coord system is flipped from the normal one, so the signs here
  144.     // are the reverse of the ones given by Kilgour.
  145.     
  146.     // Remember also that edges point DOWNWARD, and the left/right is
  147.     // from the edge's perspective, so it's backwards from the normal
  148.     // perspective!
  149.     
  150.     ODWide s1, s2;
  151.     ODWideMultiply(fDelta.x, pt.y - fHighVert->y, &s1);
  152.     ODWideMultiply(fDelta.y, pt.x - fHighVert->x, &s2);
  153.     
  154.     if( s1.hi > s2.hi )
  155.         return kRight;
  156.     else if( s1.hi < s2.hi )
  157.         return kLeft;
  158.     else
  159.         if( s1.lo==s2.lo )
  160.             return kOnTop;
  161.         else
  162.             return (s1.lo>s2.lo) ? kRight :kLeft;
  163. }
  164.  
  165.  
  166. ODBoolean
  167. PGEdge::IntersectWith( const PGEdge *edge, ODPoint § )
  168. {
  169.     return IntersectSegments( this->fHighVert->AsPoint(), this->fLowVert->AsPoint(),
  170.                               edge->fHighVert->AsPoint(), edge->fLowVert->AsPoint(),
  171.                               § );
  172. }
  173.  
  174.  
  175. //=============================================================================
  176. // PGEdge Path Construction
  177. //=============================================================================
  178.  
  179.  
  180. void
  181. PGEdge::StartPath( PGEdge *edge, const ODPoint *where )
  182. {
  183.     // Connecting two edges on the lower-edge list of an event.
  184.     // Start a new path:
  185.     
  186.     PGOutputContour *out;
  187.     if( fWrapNo>=gMinWrap && fWrapNo<=gMaxWrap ) {
  188.         out = new PGOutputContour(this,edge);
  189.         out->AddVertex(kRight,where);
  190.     } else
  191.         out = kIgnoredOutput;        // We won't be needing this contour, thanks
  192.     
  193.  
  194.     fSide = kLeft;
  195.     edge->fSide = kRight;
  196.     fOtherSide = edge;
  197.     edge->fOtherSide = this;
  198.     fOutput = edge->fOutput = out;
  199.     fMatched = edge->fMatched = kODTrue;
  200.  
  201.     BEGINLOG;
  202.     LOG("^ Creating contour %p (wrap %d) at ", fOutput, fWrapNo);
  203.     LOG(*where); LOG("\n");
  204.     ENDLOG;
  205. }
  206.  
  207.  
  208. void
  209. PGEdge::ExtendPath( PGEdge *edge, const ODPoint *where )
  210. {
  211.     // Connecting an upper with a lower edge:
  212.     
  213.     PGASSERT(fOutput!=kODNULL);
  214.     PGASSERT(edge->fOutput==kODNULL);
  215.     
  216.     // Unless the edges are parallel, we need to insert the intersection point ('where')
  217.     // into the output contour:
  218.     if( fOutput!=kIgnoredOutput && *fHighVert != edge->fHighVert->AsPoint() ) {
  219.         fOutput->AddVertex(fSide,where);
  220.         LOG("%c Added vertex (%.2f,%.2f) to contour %p\n",
  221.                     fSide==kLeft ?'<' :'>', where->x/65536.0,where->y/65536.0, fOutput );
  222.     }
  223.     edge->fSide = fSide;
  224.     edge->fOutput = fOutput;
  225.     fOutput = kODNULL;
  226.     edge->fOtherSide = fOtherSide;
  227.     fOtherSide->fOtherSide = edge;
  228.     
  229.     fMatched = edge->fMatched = kODTrue;
  230. }
  231.  
  232.  
  233. void
  234. PGEdge::MergePaths( PGEdge *edge, const ODPoint *where )
  235. {
  236.     // Connecting two upper edges:
  237.     
  238.     PGASSERT(this->fWrapNo==edge->fWrapNo);
  239.     
  240.     PGOutputContour *thisPath = fOutput;
  241.     PGOutputContour *edgePath = edge->fOutput;
  242.     PGASSERT(thisPath);
  243.     PGASSERT(edgePath);
  244.     if( ODDebug && thisPath != kIgnoredOutput )
  245.         // Same-sense paths must connect at opposite-side edges, and vice versa:
  246.         PGASSERT( (this->fSide==edge->fSide)
  247.                      != (thisPath->fSense==edgePath->fSense));
  248.     
  249.     if( fOutput != kIgnoredOutput )
  250.         fOutput->AddVertex(fSide,where);
  251.     
  252.     if( edge == fOtherSide ) {
  253.         // Path joins with itself, i.e. is closing:
  254.         PGASSERT(thisPath==edgePath);
  255.         if( fOutput != kIgnoredOutput )
  256.              fOutput->Close();
  257.         LOG("v Closing contour %p at ", thisPath);
  258.          
  259.     } else {
  260.         // Two different paths are merging together:
  261.         PGASSERT( thisPath!=edgePath || thisPath==kIgnoredOutput );
  262.         LOG("X Merging contour %p (%c) with %p (%c) at ",
  263.                 thisPath, fSide==kLeft?'<':'>',
  264.                 edgePath, edge->fSide==kLeft?'<':'>');
  265.  
  266.         // Must glue the two paths together and remove the second one:
  267.         if( fOutput != kIgnoredOutput ) {
  268.             fOutput->AppendContour(edgePath,fSide);
  269.             delete edgePath;
  270.         }
  271.         
  272.         // Introduce the end edges of the merged path to each other:
  273.         PGEdge *myOther = fOtherSide;
  274.         PGEdge *itsOther = edge->fOtherSide;
  275.         myOther->fOtherSide = itsOther;
  276.         itsOther->fOtherSide = myOther;
  277.         itsOther->fOutput = thisPath;
  278.         itsOther->fSide = (PGSide)( -(int)myOther->fSide );        // Opposite side
  279.     }
  280.  
  281.      fOutput = edge->fOutput = kODNULL;
  282.     fOtherSide = edge->fOtherSide = kODNULL;
  283.     
  284.     fMatched = edge->fMatched = kODTrue;
  285.     
  286.     LOG(*where); LOG("\n");
  287. }
  288.  
  289.  
  290. //=============================================================================
  291. // PGEdgeTable
  292. //=============================================================================
  293.  
  294.  
  295. void
  296. PGEdgeTable::Add( PGEdge *e )
  297. {
  298.     e->fLeftBundle = e->fRightBundle = kODFalse;
  299.     
  300.     for( PGEdge *el=(PGEdge*)this->First(); el; el=(PGEdge*)this->After(*el) ) {
  301.         PGSide test = el->TestPoint(e->fLowVert->AsPoint());
  302.         if( test == kRight ) {
  303.             e->AddBefore(el);
  304.             return;
  305.             
  306.         } else if( test == kOnTop ) {
  307.             // Overlapping an existing edge, so add to bundle.
  308.             // Add first if positive edge, last if negative.
  309.             if( e->fSense == kPositive ) {
  310.                 e->AddBefore(el);
  311.                 e->fRightBundle = el->fLeftBundle = kODTrue;
  312.                 
  313.             } else {
  314.                 while( el->fRightBundle )
  315.                     el = (PGEdge*)this->After(*el);
  316.                 e->AddAfter(el);
  317.                 el->fRightBundle = e->fLeftBundle = kODTrue;
  318.             }
  319.             return;
  320.         }
  321.     }
  322.     
  323.     // Must be to the right of each edge in the list...
  324.     this->AddLast(e);
  325. }
  326.  
  327.  
  328. PGEdge*
  329. PGEdgeTable::RemoveRange( PGEdge *first, PGEdge *last )
  330. {
  331.     if( !first ) {
  332.         first = (PGEdge*)this->First();
  333.         if( !first )
  334.             return kODNULL;                        // List is empty
  335.     }
  336.     if( !last )
  337.         last = (PGEdge*)this->Last();
  338.         
  339.     Link *before = first->GetPrevious();
  340.     Link *after  = last->GetNext();
  341.     
  342.     before->SetNext( after );
  343.     after->SetPrevious( before );
  344.     first->SetPrevious( kODNULL );
  345.     last->SetNext( kODNULL );
  346.     
  347.     return first;
  348. }
  349.  
  350.  
  351. void
  352. PGEdgeTable::AddRange( PGEdge *first, PGEdge *last, PGEdge *before )
  353. {
  354.     // Assumes first...last are chained together but not part of a list.
  355.     // (RemoveRange will leave them in this state.)
  356.     
  357.     if( first ) {
  358.         PGASSERT(last);
  359.         if( !before )
  360.             before = (PGEdge*)&this->fSentinel;
  361.         PGEdge *after = (PGEdge*)before->GetPrevious();
  362.         after->SetNext( first );        first->SetPrevious( after );
  363.         before->SetPrevious( last );    last->SetNext( before );
  364.     }
  365. }
  366.  
  367.  
  368. void
  369. PGEdgeTable::InsertListBefore( PGEdgeTable &list, PGEdge *before )
  370. {
  371.     PGEdge *first = (PGEdge*)list.First();
  372.     if( first ) {
  373.         PGEdge *last  = (PGEdge*)list.Last();
  374.         list.RemoveRange(first,last);
  375.         this->AddRange(first,last,before);
  376.     }
  377. }
  378.  
  379.  
  380. void
  381. PGEdgeTable::Unmatch( )
  382. {
  383.     for( Link *e = this->First(); e; e=this->After(*e) )
  384.         ((PGEdge*)e)->fMatched = kODFalse;
  385. }
  386.  
  387.  
  388. PGEdge*
  389. PGEdgeTable::FirstUnmatched( )
  390. {
  391.     return this->UnmatchedAfter((PGEdge*)&fSentinel);
  392. }
  393.  
  394.  
  395. PGEdge*
  396. PGEdgeTable::LastUnmatched( )
  397. {
  398.     return this->UnmatchedBefore((PGEdge*)&fSentinel);
  399. }
  400.  
  401.  
  402. PGEdge*
  403. PGEdgeTable::UnmatchedBefore( const PGEdge *e )
  404. {
  405.     PGASSERT(e!=kODNULL);
  406.     for( ; ; ) {
  407.         e = (PGEdge*)e->GetPrevious();
  408.         if( (Link*)e==&fSentinel )
  409.             return kODNULL;
  410.         else if( ! e->fMatched )
  411.             return (PGEdge*)e;
  412.     }
  413. }
  414.  
  415.  
  416. PGEdge*
  417. PGEdgeTable::UnmatchedAfter( const PGEdge *e )
  418. {
  419.     PGASSERT(e!=kODNULL);
  420.     for( ; ; ) {
  421.         e = (PGEdge*)e->GetNext();
  422.         if( (Link*)e==&fSentinel )
  423.             return kODNULL;
  424.         else if( ! e->fMatched )
  425.             return (PGEdge*)e;
  426.     }
  427. }
  428.